1. Cross Reference to Background Materials
The following publications (A)–(G) are not all from same fields of endeavor and terms used in some of them are not necessarily of same exact meanings as terms used herein because of differences in context. Nevertheless, the contents of these prior publications may be useful in assisting in understanding of the novel concepts presented herein, and thus these background publications may be considered as being incorporated herein by reference for purpose of providing additional background information:    (A) Resve Saleh, Shyh-Jye Jou, and A. Richard Newton, “Mixed-mode Simulation and Analog Multilevel Simulation”, Kluwer Academic Publishers, Massachusetts, 1994, ISBN 0-7923-9473-9 [This graduate level textbook is particularly useful because of its discussions about partitioning algorithms and simulation drive engines];    (B) Lawrence Pillage, Ronald Rohrer, and Chandramouli Visweswariah, “Electronic Circuit and System Simulation Methods”, McGraw-Hill Inc., New York, 1995, ISBN 0-07-0501169-6 [This textbook also includes discussions about partitioning algorithms, simulation drive engines, and the SPICE language];    (C) D. L. Beatty, R. E. Bryant, “Fast Incremental Circuit Analysis Using Extracted Hierarchy”, IEEE 1988, 25th ACM/IEEE Design Automation Conference, pp 495–500;    (D) Xiaoyi Jiang and Horst Bunke, “Optimal Quadratic-time Isomorphism of Ordered Graphs”, Elsevier Science Ltd, 1999, Journal of the Pattern Recognition Society;    (E) Peter Saviz and Omar Wing, “PYRAMID—a Hierarchical Waveform Relaxation-based Circuit Simulation Program”, IEEE, 1988, pp 442–445;    (F) Peter Saviz and Omar Wing, “Circuit Simulation by Hierarchical Waveform Relaxation”, IEEE, 1993, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 12, pp 845–860; and    (G) T. Kevenaar and D. Leenaerts, “A Flexible Hierarchical Piecewise Linear Simulator”, Elsevier Science Publishers B.V., 1991, VLSI Journal 12, pp 211–235.
2a. Reservation of Extra-Patent Rights and Resolution of Conflicts
After this disclosure is lawfully published, the owner of the present patent application has no objection to the reproduction by others of textual and graphic materials contained herein provided such reproduction is for the limited purpose of understanding the present disclosure of invention and of thereby promoting the useful arts and sciences. The owner does not however disclaim any other rights that may be lawfully associated with the disclosed materials, including but not limited to, copyrights in any computer program listings or art works or other works provided herein, and to trademark or trade dress rights that may be associated with coined terms or art works provided herein and to other otherwise-protectable subject matter included herein or otherwise derivable herefrom.
If any disclosures are incorporated herein by reference and such incorporated disclosures conflict in part or whole with the present disclosure, then to the extent of conflict, and/or broader disclosure, and/or broader definition of terms, the present disclosure controls. If such incorporated disclosures conflict in part or whole with one another, then to the extent of conflict, the later-dated disclosure controls.
2b. General Background
It is often desirable in the microelectronics industry to be able to implement physical solutions in as little time as possible for coping with new market opportunities and/or emerging problems. Computer-provided simulations are often used to predict the behaviors of to-be-manufactured electrical circuits or other like systems. This is preferably done before the electrical circuits are finalized so that design errors may be corrected and design parameters may be optimized prior to mass production. It is well known, for example, to use computers and software simulators such as SPICE for obtaining fairly accurate predictions of the analog behaviors of complex circuitry.
Other examples of analog-behavior simulators include HSPICE™ (available from Avant! Corp. of California), SPICE-3™ (available from Berkeley University of California), SPECTRE™ (available from Cadence Corp. of California), ACES™ (Adaptively Controlled Engine Simulator), and ITA™ (Interactive Timing Analysis engine). These simulators and/or simulation engines are not to be confused with digital-behavior simulators such as VHDL which predict behavior of gate-level and lower-resolution hardware descriptions (e.g., register transfer level) in the digital realm rather than at the finer resolution of transistor-level signals and in the analog realm.
SPICE-like simulations can provide fairly accurate predictions of how corresponding circuits will be behave when actually built. The predictions are preferably made not only for individual subcircuits but also for whole systems (e.g., whole integrated circuits) so that system-wide problems relating to noise and the like can be uncovered and dealt with.
However, SPICE-like simulation of whole systems becomes more difficult and problematic as the industry continues its relentless trek of scaling down to smaller and smaller device geometries as is predicted by Moore's Law and of cramming more interconnected components into a system. An example of such down scaling is the recent shift from micron-sized channels toward deep submicron sized transistor lengths. Because of this, circuit designers are able to cram exponentially larger numbers of basic components or ‘elements’ (e.g., transistors, diodes, capacitors) into a given integrated circuit (IC) or other such, mass-producible device.
Due to the shortened time-to-market pressures in the industry, the designers of these mass-producible systems (e.g., IC's) want the makers of pre-fabrication SPICE-like simulators to come up with new ways for quickly and accurately predicting the system-wide behaviors of these exponentially more dense and more complex, interconnected system designs. This is not as easily done as it may sound.
In designs that employ hierarchical structuring, however, opportunities do exist for taking advantage of the redundant behaviors that are sometimes exhibited by structurally redundant subcomponents (isomorphic subsets) of the hierarchical structure. Rather than instantiating and simulating individually, all the redundant subcomponents of a system, it is possible to pick one of many, alike subcomponents and to consider the picked subcomponent as having a behavior that is representative of the behaviors of the others. The predicted behavior results obtained for the representative one subcomponent may be duplicated for the others without repeating computationally-intense simulation processing for each of the mirror-wise alike subcomponents. As such, significant amounts of computing time and computational resources may be saved if redundant subcomponents can be identified and their behaviors can be predicted in this way.
Examples of integrated circuits which tend to exhibit hierarchical structuring include high-density memory chips such as SRAMs, DRAMs, EEPROMs, etc. Parallel data processing systems and telecommunication systems also tend to have hierarchical structures with redundant subcomponents.
Given the above, there is still the problem of how to efficiently identify redundant subcomponents and how to efficiently take advantage of their redundant behaviors during simulation of hierarchical systems. Also there are times when end users do not want to take advantage of hierarchical structuring and instead want to simulate a, so-called fully flattened model. There is the problem of how to provide end users with the capability under one system of performing both hierarchically-mapped and fully flattened model simulations.